Many devices, especially mobile devices such as smartphones and computing tablets, store executable files in a compressed form in nonvolatile memory (such a FLASH memory). For example, smartphones and tablets which use an Android operating system, for example, store the executable instructions for virtually every application or program as a compressed file in a FLASH memory, enabling the use of a smaller and less expensive FLASH memory than would otherwise be required. In addition, in many devices, the operating system itself or parts of the operating system may also be stored as compressed files. These compressed files must be decompressed, without loss of data, into the complete executable file before the corresponding application can execute, i.e., before the application can be launched and start operating.
Such an executable file may be compressed using any compression algorithm or methodology. Many are compressed using the GNU “Gzip” or other variations, such as Linux “Gunzip”, for example and without limitation. These compressed files are typically comprised of a plurality of variable length blocks, with run length encoding (“RLE”), which creates significant data dependencies throughout the entire compressed file. For example, Gzip employs RLE across multiple blocks and requires a moving window of about 32 Kbytes, i.e., decoding a current symbol may reference an earlier symbol as far back as 32 Kbytes within the file. In addition, compression algorithms such as Gzip do not preserve data which might be useful in the decompression, such as the actual length of any given block. While the compression of a file may be done in parallel, such as by dividing a file into segments and compressing each segment, it has been widely believed (and publicly stated by the creator of Gzip) that it is “impossible” to decompress such compressed files in parallel, largely due to the difficulties mentioned above.
Historically, the time required for decompression of an executable file was not a concern because the compressed executable file was required to be decompressed only once, such as during initial installation of the application, at which point the decompressed executable file would be stored in memory and be available for execution. Now, however, while less space in nonvolatile memory may be advantageous for various devices, the trade-off is that every time such an application is launched (e.g., for every mobile telephone call), it must be read from the nonvolatile memory and decompressed, which takes considerable time, namely, enough time delay (or lag time) to be noticeable by the consumer or other user.
Various decompression programs, such as “pigz”, purport to provide for parallel decompression of Gzip compressed data. The pigz program, however, only utilizes a single, serial thread for the actual decompression of the compressed data, and is parallel only insofar as it provides additional threads in parallel for non-decompression functionality, such as reading, writing, and check calculations.
Accordingly, a need remains for an apparatus, system, method, and software for data-dependent parallel processing, to accelerate executable file processing, application processing, and data processing. For example, such an apparatus, system, method, and software should provide for acceleration of the decompression of compressed files, such as through the parallel decompression of compressed executable files, including operating systems and program applications. Such an apparatus, system, method, and software further should provide such acceleration for compression algorithms which have been viewed as “impossible” to accelerate, such as Gzip, and further should be extendable to the acceleration of the operation and execution of other types of computing applications, such as operating systems, Linux kernel, Java, Javascript, AOT, gaming applications, and so on, to result in faster boot operations, faster execution of an application, and an enhanced user experience.